НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №3 з навчальної дисципліни “Програмування складних алгоритмів” Тема: МЕТОДИ СОРТУВАННЯ Варіант №12  Київ 2022 Мета: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Теоретична частина Сортування масиву — один з найбільш розповсюджених процесів обробки даних. Завдяки йому здійснюється розміщеня об’ектів у визначеному порядку, наприклад, чисел за зростанням або за спаданням їх значень, прізвищ у алфавітному порядку тощо. Існують різні методи сортування, серед них — обмінне сортування (метод «пухирця», «шейкер-сортування), сортування вибором, сортування вставками, швидке сортування, сортування Шелла, пірамідальне сортування, сортування обчисленням адреси, сортування порозрядним групуванням тощо. Ці методи відрізняються швидкістю отримання результату, складністю і універсальністю. Розглянемо три методи сортування: обміном, вибором та вставками. Названі методи легко описуються у формі чітких алгоритмiв і передбачають нескладну програмну реалізацію, крім того вони цікаві тим, що моделюють природну поведінку люди­ни, яка здійснює сортування вручну. З іншого боку, вказані ме­тоди не досить ефективні і використовуються у випадках, коли необхідно відсортувати масиви невеликого розміру. Обмінне сортування проілюструємо простим сортуванням обмiном — методом «пухирця», який здійснюється шляхом перестановки елементів за визначеним правилом. Головні складові методу «пухирця»: крок сортування містить перегляд елементів масиву з по­чатку до кінця, при цьому розглядаються пари сусідніх елементів; елементи деякої пари міняються місцями у випадку, коли їх послідовність розташування не відповідає умові сортуван­ня (за зростанням або за спаданням). Сортування за вставками Ще один алгоритм, розроблений для впорядкування масивів, - алгоритм сортування вставок. Даний алгоритм (як і інші розглянуті на нашому сайті) досить простий. Він складається з двох циклів (один вкладений в межах іншого). Перший цикл робить прохід через масив, а другий - рух оброблюваних елементів. Часова складність Розмір Складність алгоритму Час роботи методом вставок Час роботи методом бульбашки  10х10 O(n^2) Квадратичний алгоритм 1,25e-05 9,07e-0,6  50х50  5,531e-0,5 0,00401715  100х100  0,0108855158 0,0790612   Завдання: Розробити програму з алгоритмом згідно варіанту з використанням методів сортування. Оцінити час виконання та складність алгоритму. Завдання до Варіанту_12 Метод сортування вставками
+Метод сортування бульбашка (за бажанням)  Результати виконання лабораторної роботи:

 Код: //Лабораторна робота №3_ПСА //ТР-15_Ткаченко_Майя, Варіант_12 #include <iostream> #include <algorithm> #include "chrono" using namespace std; Висновки В ході виконання даної лабораторної роботи було розглянуто різні методи сортування масивів. Виконано завдання згідно варіанту, проведено сортування по схемі, методом вставок, а також в якості методу сортування за бажанням, було вибрано метод бульбашки. Також програма виводить окремо час виконання кожного алгоритму.